#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int maxn = 2e3 + 10;
int dp[maxn][maxn][2]; // 前 i 个选了 j 个, 并且不在(0) 第 i 个工作, 或者在 第 i 个工作

int n,m;
int arr[maxn];

void solve(){
	cin>>n>>m;
	for (int i=1;i<=n;i++) {
		int a;
		cin>>a;
		arr[i]=a;
	}
	memset(dp, -0x3f, sizeof(dp));
	dp[1][0][0]=dp[1][1][1]=0; // 第一个不选, 选了但是需上交
	
	for (int i=1;i<=n;i++) {
		dp[i][0][0]=0;
	}
	
	for (int i=2;i<=n;i++) { // 遍历 i 个仓库
		for (int j=1;j<=min(i,m);j++) {
			dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]);
			dp[i][j][1] = max(dp[i-1][j-1][0], dp[i-1][j-1][1]+arr[i]); // 是第一个需要交出去, 不是就不用
		}
	}
	
	int ans = max(dp[n][m][0], dp[n][m][1]);
	
	// 强制连接
	memset(dp, -0x3f, sizeof(dp));
	dp[1][1][1] = arr[1]; // 只需与 n 连接起来即可,唯一可能产生影响的就是 第 n 个选了
	dp[1][0][0]=dp[1][1][0]=0;
	
	for (int i=1;i<=n;i++) {
		dp[i][0][0]=0;
	}
	
	for (int i=2;i<=n;i++) { // 遍历 i 个仓库
		for (int j=1;j<=min(i,m);j++) {
			dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]);
			dp[i][j][1] = max(dp[i-1][j-1][0], dp[i-1][j-1][1]+arr[i]); // 是第一个需要交出去, 不是就不用
		}
	}
	
	ans = max(ans, dp[n][m][1]); // 注意第二次 DP 我们考虑的就是 第 n 个已经被选了, 所以直接就是 dp[n][m][1]
	cout <<ans<<'\n';
	
	
}
	

signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}
